#include <iostream>
#include <queue>
#include <vector>
#include <cassert>
#include "../head/struct.h"

using namespace std;

/**
 * 102 : 二叉树层序遍历
 * 通过队列层序遍历二叉树
 **/
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
		if(root == NULL)
			return res;
		queue<pair<TreeNode*, int>> q;	// 存储 节点 + 第几层
		q.push(make_pair(root, 0));

		while(!q.empty()){
			TreeNode* node = q.front().first();		// 从队列中取出队首元素
			int level = q.front().second;			// 层级信息
			q.pop();								// 队首元素出队
			
			// 当前节点所在的层 ，是否是当前result中包含的层数
			if(level == res.size()){	// rersult 中不包含该层 层数应该小于result.
				res.push_back(vector<int()>);
			}
			assert(level < res.size());
			
			res[level].push_back(node->val);
			if(node->left)
				q.push(make_pair(node->left, level + 1));
			if(node->right)
				q.push(make_pair(node->right, level + 1));
		}
		return res;
    }
};
